#include <queue>
#include <vector>
using namespace std;

// 整体思路： 使用两个堆（大根堆和小根堆）来维护数据流的中位数。
//           1. 小根堆（large）保存较大的一半数据，大根堆（small）保存较小的一半数据。
//            2. 保持两个堆的大小平衡，确保它们的大小差不超过1。
class MedianFinder
{
private:
    // 大根堆（保存较小的一半）
    priority_queue<int, vector<int>, less<int>> small;
    // 小根堆（保存较大的一半）
    priority_queue<int, vector<int>, greater<int>> large;

public:
    MedianFinder() {}

    void addNum(int num)
    {
        small.push(num);

        // 保证有序性：大根堆最大值 < 小根堆最小值
        if (!small.empty() && !large.empty() && small.top() > large.top())
        {
            large.push(small.top());
            small.pop();
        }

        // 保证平衡：两个堆的大小差不超过 1
        if (small.size() > large.size() + 1)
        { // 大根堆多了
            large.push(small.top());
            small.pop();
        }
        else if (large.size() > small.size() + 1)
        { // 小根堆多了
            small.push(large.top());
            large.pop();
        }
    }

    double findMedian()
    {
        if (small.size() > large.size())
        {
            return small.top();
        }
        else if (large.size() > small.size())
        {
            return large.top();
        }
        else
        {
            return (small.top() + large.top()) / 2.0;
        }
    }
};
